//
//  ViewController.swift
//  LeetCodeSwift
//
//  Created by XFB on 2019/7/11.
//  Copyright © 2019 XFB. All rights reserved.
//  https://leetcode-cn.com/problems/reverse-string/comments/ 反转字符串

import UIKit

class ViewController: UIViewController {
    
    override func viewDidLoad() {
        super.viewDidLoad()
        
        /**
         给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
         你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
         示例:
         给定 nums = [2, 7, 11, 15], target = 9
         所以返回 [0, 1]
         */
        let nums = [2, 7, 11, 15]
        let target = 9
        let twoCountSum = TwoCountSum()
        print(twoCountSum.twoSum(nums, target))
        print(twoCountSum.twoSum1(nums, target))
        print(twoCountSum.twoSum2(nums, target))

        
        /**
         给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
         注意：答案中不可以包含重复的三元组。
         例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
         满足要求的三元组集合为：
         [
         [-1, 0, 1],
         [-1, -1, 2]
         ]
         */
        let nums1 = [-1, 0, 1, 2, -1, -4]
        let threeCountSum = ThreeCountSum()
        print(threeCountSum.threeSum(nums1))
        print(threeCountSum.threeSum1(nums1))
        print(threeCountSum.threeSum2(nums1))
        
        
        /**
         给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
         注意：
         答案中不可以包含重复的四元组。
         示例：
         给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
         满足要求的四元组集合为：
         [
         [-1,  0, 0, 1],
         [-2, -1, 1, 2],
         [-2,  0, 0, 2]
         ]
         先找好i = 0, j = i + 1, 在定左右边界
         */
        
        /// -2 -1 0 0      1 2
        let nums2 = [1, 0, -1, 0, -2, 2]
        let target2 = 0
        let fourCountSum = FourCountSum()
        print(fourCountSum.fourSum(nums2, target2))
        print(fourCountSum.fourSum1(nums2, target2))


        
        /**
         给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
         不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
         示例 1:
         给定数组 nums = [1,1,2],
         函数应该返回新的长度 2, 并且原数组 nums 的【前两个元素被修改为 1, 2】。
         你不需要考虑数组中超出新长度后面的元素。
       
         示例 2:
         给定 nums = [0,0,1,1,1,2,2,3,3,4],
         函数应该返回新的长度 5, 并且原数组 nums 的【前五个元素被修改为 0, 1, 2, 3, 4】。
         你不需要考虑数组中超出新长度后面的元素。
         */
//        var nums3 = [1,1,2]
        var nums3 = [0,0,1,1,1,2,2,3,3,4]
        let removeDuplicates = RemoveDuplicatesFromSortedArrayI()
        print(removeDuplicates.removeDuplicates(&nums3))

        
        /**
         给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
         不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
         元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
         
         示例 1:
         给定 nums = [3,2,2,3], val = 3,
         函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
         你不需要考虑数组中超出新长度后面的元素。
         
         示例 2:
         给定 nums = [0,1,2,2,3,0,4,2], val = 2,
         函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
         注意这五个元素可为任意顺序。
         你不需要考虑数组中超出新长度后面的元素。
         */
        
        var nums4 = [0,1,2,2,3,0,4,2]
        let target4 = 2
        let removeDuplicates1 = RemoveDuplicatesFromSortedArrayII()
        print(removeDuplicates1.removeElement(&nums4, target4))
        print(removeDuplicates1.removeElement1(&nums4, target4))

        
        /**
         给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
         你可以假设数组中无重复元素。
         示例 1:
         输入: [1,3,5,6], 5
         输出: 2
         
         示例 2:
         输入: [1,3,5,6], 2
         输出: 1
         
         示例 3:
         输入: [1,3,5,6], 7
         输出: 4
         
         示例 4:
         输入: [1,3,5,6], 0
         输出: 0
         */
        var nums5 = [1,3,5,6]
        var target5 = 5
        let searchInsertPosition = SearchInsertPosition()
        print(searchInsertPosition.searchInsert(nums5, target5))
        print(searchInsertPosition.searchInsert1(nums5, target5))
        print(searchInsertPosition.searchInsert2(nums5, target5))

        
        /**
         给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
         例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
         与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
         */
        var num6 = [-1, 2, 1, -4]
        var target6 = 1
        let acceptThreeCountSum = AcceptThreeCountSum()
        print(acceptThreeCountSum.threeSumClosest(num6, target6))
        
        
        /**
         给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
         有效字符串需满足：
         左括号必须用相同类型的右括号闭合。
         左括号必须以正确的顺序闭合。
         注意空字符串可被认为是有效字符串。
         
         示例 1:
         输入: "()"
         输出: true
         
         示例 2:
         输入: "()[]{}"
         输出: true
         
         示例 3:
         输入: "(]"
         输出: false
         
         示例 4:
         输入: "([)]"
         输出: false
         
         示例 5:
         输入: "{[]}"
         输出: true
         */
        var nums7 = "{[]}"
        let validParenthesis = ValidParenthesis()
        print(validParenthesis.isValid(nums7))
        
        
        /**
         给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
         说明: 【***重点***】 m 和 n
         初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
         你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
         示例:
         输入:
         nums1 = [1,2,3,0,0,0], m = 3
         nums2 = [2,5,6],       n = 3
         
         输出: [1,2,2,3,5,6]
         */
        var numsM = [1, 2, 3, 0, 0, 0]
        var numsN = [2, 5, 6]
        var targetM = 3
        var targetN = 3
        let mergeSortedArray = MergeSortedArray()
        print(mergeSortedArray.merge(&numsM, targetM, numsN, targetN))
        
        
        
        /**
         给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。
         如果不存在最后一个单词，请返回 0 。
         说明：一个单词是指由字母组成，但不包含任何空格的字符串。
         示例:
         输入: "Hello World"
         输出: 5
         
         字符串遍历：
         */
//        let wordString = "Hello World"
        var wordString = "123456789"
        let lastWordLength = LastWordLength()
        print(lastWordLength.lengthOfLastWord(wordString))
        
        
        /**
         给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
         示例 1:
         输入: [3,0,1]
         输出: 2
         
         示例 2:
         输入: [9,6,4,2,3,5,7,0,1]
         输出: 8
         */
        
//        let nums8 = [3,0,1]
        let nums8 = [9,6,4,2,3,5,7,0,1]
        let missNumber = MissNumber()
        print(missNumber.missingNumber(nums8))
        print(missNumber.missingNumber1(nums8))

        
        /**
         罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
         字符          数值
         I             1
         V             5
         X             10
         L             50
         C             100
         D             500
         M             1000
         
         例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
         通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
         
         I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
         X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
         C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
         给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
         
         示例 1:
         输入: "III"
         输出: 3
         
         示例 2:
         输入: "IV"
         输出: 4
         
         示例 3:
         输入: "IX"
         输出: 9
         
         示例 4:
         输入: "LVIII"
         输出: 58
         解释: L = 50, V= 5, III = 3.
         
         示例 5:
         输入: "MCMXCIV"
         输出: 1994
         解释: M = 1000, CM = 900, XC = 90, IV = 4.
         
         */
        let romanString = "MCMXCIV"
        let romanToInteger = RomanToInteger()
        print(romanToInteger.romanToInt(romanString))
        
        
        /**
         假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
         
         注意：
         你可以假设胃口值为正。
         一个小朋友最多只能拥有一块饼干。
         
         示例 1:
         输入: [1,2,3], [1,1]
         输出: 1
         
         解释:
         你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
         虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
         所以你应该输出1。
         
         示例 2:
         输入: [1,2], [1,2,3]
         输出: 2
         
         解释:
         你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
         你拥有的饼干数量和尺寸都足以让所有孩子满足。
         所以你应该输出2.
         */
        let gSortedArray = [1,2,3]
        let sSortedArray = [1,1]
        let assignCookie = AssignCookies()
        print(assignCookie.findContentChildren(gSortedArray, sSortedArray))
        
        
        
        /**
         如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
         
         例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
         给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
         
         示例 1:
         输入: [1,7,4,9,2,5]
         输出: 6
         解释: 整个序列均为摆动序列。
         
         示例 2:
         输入: [1,17,5,10,13,15,10,5,16,8]
         输出: 7
         解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
         
         示例 3:
         输入: [1,2,3,4,5,6,7,8,9]
         输出: 2
         
         */
//        let nums9 = [1,7,4,9,2,5]
//        let nums9 = [1,17,5,10,13,15,10,5,16,8]
        let nums9 = [1,2,3,4,5,6,7,8,9]
        let wiggleSubsequence = WiggleSubsequence()
        print(wiggleSubsequence.wiggleMaxLength(nums9))
        
        
//        var listNode = 1 -> 2 -> 3 -> 4 -> 5 -> nil
        let listNode = ["1", "2", "3", nil]
        let reverseLinkedList = ReverseLinkedList()
        
        
        var nums10 = [5, 2, 6, 0, 9]
//        var nums10 = [2, 3, 5, 7, 1, 4, 6, 15, 5, 2, 7, 9, 10, 15, 9, 17, 12]
//        var nums10 = [2, 8, 9, 10, 4, 5, 6, 7]
        let varietySorted = VarietySorted()
        /// 冒泡排序
        print(varietySorted.BubbleSorted(nums10))
        /// 直接插入排序
        print(varietySorted.InsertSorted(nums10))
        /// 折半插入排序
        print(varietySorted.InsertSorted3(nums10))

        
        
        /// 快速排序
        let low = 0
        let high = nums10.count - 1
        print(varietySorted.QuickSorted(nums: &nums10, leftBound: low, rightBound: high))
        /// 希尔排序
        print(varietySorted.ShellSorted(nums10))
        /// 归并排序
        let L = 0
        let R = nums10.count - 1
        let M = (R - L) / 2 + 1
        print(varietySorted.MergeSorted(nums10, L, M, R))
        print(varietySorted.MergeSort(nums10, L, R))

        
        /// 链表
        var linkedListStr = LinkedList<String>()
        linkedListStr.append(data: "James")
        linkedListStr.append(data: "Jordan")
        linkedListStr.append(data: "Fearless")
        linkedListStr.append(data: "Wade")
        linkedListStr.append(data: "Curry")
        print("\(linkedListStr)")
        
        let linkedListNumber = LinkedList<Int>()
        linkedListNumber.append(data: 1)
        linkedListNumber.append(data: 2)
        linkedListNumber.append(data: 3)
        linkedListNumber.append(data: 4)
        linkedListNumber.append(data: 5)
        print("\(linkedListNumber)")

        let nodeString = Node.init(data: "Curry")
        print("\(linkedListStr.remove(node: nodeString))")
        print("\(linkedListStr)")

        linkedListStr.removeAllNode()
        print("\(linkedListStr)")

        
        
        
        
        
        
        
        
        
        /**
         2
         反转字符串
         编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
         不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
         你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
         
         示例 1：
         输入：["h","e","l","l","o"]
         输出：["o","l","l","e","h"]
         
         示例 2：
         输入：["H","a","n","n","a","h"]
         输出：["h","a","n","n","a","H"]
         */
        var characterArray = [Character]()
        characterArray.append("h")
        characterArray.append("e")
        characterArray.append("l")
        characterArray.append("l")
        characterArray.append("o")
        
        func reverseString(_ s: inout [Character]) {
            
            guard !s.isEmpty else {
                return
            }
            
            var i = 0
            var j = s.count - 1
            var temp : Character
            
            /// 如果数组个数为单 <
            /// 如果数组个数为双 <=
            while i <= j {
                
                temp = s[i]
                s[i] = s[j]
                s[j] = temp
                
                i = i + 1
                j = j - 1
            }
            return
        }
        
        reverseString(&characterArray)
//        print("\(characterArray)")
    }
}

